#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct QueueNode {
    struct TreeNode* treeNode;
    struct QueueNode* next;
};

struct Queue {
    struct QueueNode* front;
    struct QueueNode* rear;
};

struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

struct Queue* createQueue() {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->front = NULL;
    queue->rear = NULL;
    return queue;
}

void enqueue(struct Queue* queue, struct TreeNode* treeNode) {
    struct QueueNode* newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    newNode->treeNode = treeNode;
    newNode->next = NULL;
    if (queue->rear == NULL) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

struct TreeNode* dequeue(struct Queue* queue) {
    if (queue->front == NULL) {
        printf("队列为空\n");
        exit(1);
    }
    struct QueueNode* temp = queue->front;
    struct TreeNode* treeNode = temp->treeNode;
    queue->front = queue->front->next;
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    free(temp);
    return treeNode;
}

int isEmpty(struct Queue* queue) {
    return (queue->front == NULL);
}

void reverseLevelOrder(struct TreeNode* root) {
    if (root == NULL)
        return;
    struct Queue* queue = createQueue();
    struct TreeNode* stack[100]; // 假设最多有100个结点
    int top = -1;
    enqueue(queue, root);
    while (!isEmpty(queue)) {
        struct TreeNode* currentNode = dequeue(queue);
        stack[++top] = currentNode;
        if (currentNode->left != NULL)
            enqueue(queue, currentNode->left);
        if (currentNode->right != NULL)
            enqueue(queue, currentNode->right);
    }
    while (top >= 0) {
        printf("%d ", stack[top--]->data);
    }
}

int main() {
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);

    reverseLevelOrder(root);
    printf("\n");

    return 0;
}
